import java.util.*;

/**
 * @author LKQ
 * @date 2022/5/12 15:28
 * @description 并查集, 一种树形数据结构，用于处理一些不交集的合并和查询问题，支持两种操作；
 * 查找 Find: 确定某个元素处于那个子集中
 * 合并 Union: 将两个子集合并称一个集合
 */
public class UnionFind {

    /**
     * 记录某个结点的爸爸是谁，特别规定，祖先的爸爸是自己
     */
    int[] parent;

    public UnionFind(int n) {
        parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }
    public int find(int x) {
        if (parent[x] != x) {
            // 发现父节点不是自己，那么继续寻找父节点，这里其实顺手进行了路径压缩，让每个结点连接到根上
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    public void union(int x , int y) {
        parent[find(x)] = find(y);
    }
}


